package com.fenqing.leetcode.code.t0_200.t100_200;

import com.fenqing.annotations.Execute;
import com.fenqing.core.Topic;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author fenqing
 */
public class Topic200_1 extends Topic {
    /**
     * 构造器
     *
     * @param input 输入
     */
    public Topic200_1(String input) {
        super(input);
    }

    @Execute
    public int numIslands(char[][] grid) {
        int len = grid.length;
        int len2 = grid[0].length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len2; j++) {
                char ch = grid[i][j];
                if (ch == '1') {
                    count++;
                    grid[i][j] = '0';
                    bfs(grid, i, j);
                }
            }
        }
        return count;
    }

    public void bfs(char[][] grid, int x, int y){
        int xLen = grid.length;
        int yLen = grid[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{x, y});
        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int x1 = poll[0], y1 = poll[1];
            int xl = x1 - 1, xr = x1 + 1, yt = y1 - 1, yb = y1 + 1;
            // 左边
            if (xl >= 0 && grid[xl][y1] == '1'){
                grid[xl][y1] = '0';
                queue.add(new int[]{xl, y1});
            }
            // 右边
            if (xr < xLen && grid[xr][y1] == '1'){
                grid[xr][y1] = '0';
                queue.add(new int[]{xr, y1});
            }
            // 上边
            if (yt >= 0 && grid[x1][yt] == '1'){
                grid[x1][yt] = '0';
                queue.add(new int[]{x1, yt});
            }
            //下边
            if (yb < yLen && grid[x1][yb] == '1'){
                grid[x1][yb] = '0';
                queue.add(new int[]{x1, yb});
            }
        }
    }

    public static void main(String[] args) {
        Topic200_1 topic200 = new Topic200_1("[ [\"1\",\"1\",\"0\",\"0\",\"0\"], [\"1\",\"1\",\"0\",\"0\",\"0\"], [\"0\",\"0\",\"1\",\"0\",\"0\"], [\"0\",\"0\",\"0\",\"1\",\"1\"] ]");
        int run = topic200.run();
        System.out.println(run);
    }

}
